using System;

namespace RBT
{
    public class RBTree : object
    {
        /// <summary>
        /// The number of nodes contained in the tree
        /// </summary>
        private int _intCount;
        /// <summary>
        /// A simple randomized hash code. 
        /// The hash code could be used as a key if it is "unique" enough.
        /// Note: The IComparable interface would need to be replaced with the Type:int.
        /// </summary>
        private int _intHashCode;
        /// <summary>
        /// Identifies the owner of the tree
        /// </summary>
        private string _strIdentifier;
        /// <summary>
        /// The tree
        /// </summary>
        private RBTreeNode _rbTree;
        /// <summary>
        /// SentinelNode is convenient way of indicating a leaf nextNode.
        /// </summary>
        public static RBTreeNode SentinelNode;
        /// <summary>
        /// The nextNode that was last found; used to optimize searches
        /// </summary>
        private RBTreeNode _lastNodeFound;
        /// <summary>
        /// Random generator
        /// </summary>
        private Random _random = new Random();
        /// <summary>
        /// Constructor
        /// </summary>
        public RBTree()
        {
            _strIdentifier = base.ToString() + _random.Next();
            _intHashCode = _random.Next();
            //set up the sentinel nextNode.
            //the sentinel nextNode is the key to a successfull
            //implementation and for understanding 
            //the red-black tree properties.
            SentinelNode = new RBTreeNode
            {
                Left = null,
                Right = null,
                Parent = null,
                Color = RBTreeNode.Black
            };
            _rbTree = SentinelNode;
            _lastNodeFound = SentinelNode;
        }
        /// <summary>
        /// Constructor with identifying
        /// </summary>
        /// <param name="strIdentifier">Identifier</param>
        public RBTree(string strIdentifier)
        {
            _intHashCode = _random.Next();
            _strIdentifier = strIdentifier;
        }
        /// <summary>
        /// Adds key and value
        /// </summary>
        /// <param name="key">IComparable key value</param>
        /// <param name="data">Object data value</param>
        public void Add(IComparable key, object data)
        {
            if (key == null || data == null)
                throw (new RBTreeException("RBNode key and data must not be null"));
            //traverse tree - find where next node belongs
            int result;
            //create new next node
            var node = new RBTreeNode();
            var temp = _rbTree;//grab the RBTree next node of the tree
            while (temp != SentinelNode)//find Parent
            {	
                node.Parent = temp;
                result = key.CompareTo(temp.Key);
                if (result == 0)
                    throw (new RBTreeException("A Node with the same key already exists"));
                temp = result > 0 ? temp.Right : temp.Left;
            }
            //setup nextNode
            node.Key = key;
            node.Data = data;
            node.Left = SentinelNode;
            node.Right = SentinelNode;
            //insert next node into tree starting at parent's location
            if (node.Parent != null)
            {
                result = node.Key.CompareTo(node.Parent.Key);
                if (result > 0)
                    node.Parent.Right = node;
                else
                    node.Parent.Left = node;
            }
            else
                _rbTree = node;//first next node added
            RestoreAfterInsert(node);//restore RB properities
            _lastNodeFound = node;
            _intCount++;
        }
        /// <summary>
        /// Additions to RB trees usually destroy the RB properties.
        /// Examine the tree and restore. Rotations are normally required to restore it.
        /// </summary>
        /// <param name="xNode">RB tree node</param>
        private void RestoreAfterInsert(RBTreeNode xNode)
        {
            //xNode and y are used as variable names for brevity, 
            //in a more formal implementation
            RBTreeNode y;
            //maintain RB tree properties after adding xNode
            while (xNode != _rbTree && xNode.Parent.Color == RBTreeNode.Red)
            {
                //Parent nextNode is .Colored red; 
                if (xNode.Parent == xNode.Parent.Parent.Left)//determine traversal path			
                {//is it on the Left or Right subtree?
                    y = xNode.Parent.Parent.Right;//get uncle
                    if (y != null && y.Color == RBTreeNode.Red)
                    {//uncle is red; change xNode's Parent and uncle to black
                        xNode.Parent.Color = RBTreeNode.Black;
                        y.Color = RBTreeNode.Black;
                        //grandparent must be red. Every red nextNode that is not 
                        //a leaf has only black children 
                        xNode.Parent.Parent.Color = RBTreeNode.Red;
                        xNode = xNode.Parent.Parent;//continue loop with grandparent
                    }
                    else
                    {
                        //uncle is black; determine if xNode is greater than Parent
                        if (xNode == xNode.Parent.Right)
                        {//xNode is greater than Parent; rotate Left
                            //make xNode a Left child
                            xNode = xNode.Parent;
                            RotateLeft(xNode);
                        }
                        //xNode is less than Parent
                        xNode.Parent.Color = RBTreeNode.Black;//make Parent black
                        xNode.Parent.Parent.Color = RBTreeNode.Red;//make grandparent black
                        RotateRight(xNode.Parent.Parent);//rotate right
                    }
                }
                else
                {//xNode's Parent is on the Right subtree
                    //this code is the same as above with "Left" and "Right" swapped
                    y = xNode.Parent.Parent.Left;
                    if (y != null && y.Color == RBTreeNode.Red)
                    {
                        xNode.Parent.Color = RBTreeNode.Black;
                        y.Color = RBTreeNode.Black;
                        xNode.Parent.Parent.Color = RBTreeNode.Red;
                        xNode = xNode.Parent.Parent;
                    }
                    else
                    {
                        if (xNode == xNode.Parent.Left)
                        {
                            xNode = xNode.Parent;
                            RotateRight(xNode);
                        }
                        xNode.Parent.Color = RBTreeNode.Black;
                        xNode.Parent.Parent.Color = RBTreeNode.Red;
                        RotateLeft(xNode.Parent.Parent);
                    }
                }
            }
            if (_rbTree != null) 
                _rbTree.Color = RBTreeNode.Black;//RBTree should always be black
        }
        /// <summary>
        /// Rebalance the tree by rotating the nodes to the left 
        /// </summary>
        /// <param name="xNode">RB tree node</param>
        public void RotateLeft(RBTreeNode xNode)
        {
            //pushing nextNode xNode down and to the Left to balance the tree.
            //xNode's Right child (y) replaces xNode (since y > xNode),
            //and y's Left child becomes xNode's Right child (since it's < y but > xNode).
            var y = xNode.Right;//get xNode's Right nextNode, this becomes y
            //set xNode's Right link
            xNode.Right = y.Left;//y's Left child's becomes xNode's Right child
            //modify parents
            if (y.Left != SentinelNode)
                y.Left.Parent = xNode;//sets y's Left Parent to xNode
            if (y != SentinelNode)
                y.Parent = xNode.Parent;//set y's Parent to xNode's Parent
            if (xNode.Parent != null)
            {//determine which side of it's Parent xNode was on
                if (xNode == xNode.Parent.Left)
                    xNode.Parent.Left = y;//set Left Parent to y
                else
                    xNode.Parent.Right = y;//set Right Parent to y
            }
            else
                _rbTree = y;//at RBTree, set it to y
            //link xNode and y 
            y.Left = xNode;//put xNode on y's Left 
            if (xNode != SentinelNode)//set y as xNode's Parent
                xNode.Parent = y;
        }
        /// <summary>
        /// Rebalance the tree by rotating the nodes to the right
        /// </summary>
        /// <param name="xNode">RB Tree node</param>
        public void RotateRight(RBTreeNode xNode)
        {
            //pushing nextNode xNode down and to the Right to balance the tree. 
            //xNode's Left child (y) replaces xNode (since xNode < y), 
            //and y's Right child becomes xNode's Left child (since it's < xNode but > y).
            var y = xNode.Left;//get xNode's Left nextNode, this becomes y
            //set xNode's Right link
            xNode.Left = y.Right;//y's Right child becomes xNode's Left child
            //modify parents
            if (y.Right != SentinelNode)
                y.Right.Parent = xNode;//sets y's Right Parent to xNode
            if (y != SentinelNode)
                y.Parent = xNode.Parent;//set y's Parent to xNode's Parent
            if (xNode.Parent != null)//null=_rbTree, could also have used _rbTree
            {//determine which side of it's Parent xNode was on
                if (xNode == xNode.Parent.Right)
                    xNode.Parent.Right = y;//set Right Parent to y
                else
                    xNode.Parent.Left = y;//set Left Parent to y
            }
            else
                _rbTree = y;//at _rbTree, set it to y
            //link xNode and y 
            y.Right = xNode;//put xNode on y's Right
            if (xNode != SentinelNode)//set y as xNode's Parent
                xNode.Parent = y;
        }
        /// <summary>
        /// Gets the data object associated with the specified key
        /// </summary>
        /// <param name="key">Key</param>
        /// <returns>Object data</returns>
        public object GetData(IComparable key)
        {
            int result;
            var treeNode = _rbTree;//begin at root
            //traverse tree until nextNode is found
            while (treeNode != SentinelNode)
            {
                result = key.CompareTo(treeNode.Key);
                if (result == 0)
                {
                    _lastNodeFound = treeNode;
                    return treeNode.Data;
                }
                treeNode = result < 0 ? treeNode.Left : treeNode.Right;
            }
            throw (new RBTreeException("RB Tree Node key was not found"));
        }
        /// <summary>
        /// Gets the minimum key value
        /// </summary>
        /// <returns>IComparable key</returns>
        public IComparable GetMinKey()
        {
            var treeNode = _rbTree;
            if (treeNode == null || treeNode == SentinelNode)
                throw (new RBTreeException("RB tree is empty"));
            //traverse to the extreme left to find the smallest key
            while (treeNode.Left != SentinelNode)
                treeNode = treeNode.Left;
            _lastNodeFound = treeNode;
            return treeNode.Key;
        }
        /// <summary>
        /// Gets the maximum key value
        /// </summary>
        /// <returns>IComparable key</returns>
        public IComparable GetMaxKey()
        {
            var treeNode = _rbTree;
            if (treeNode == null || treeNode == SentinelNode)
                throw (new RBTreeException("RB ree is empty"));
            //traverse to the extreme right to find the largest key
            while (treeNode.Right != SentinelNode)
                treeNode = treeNode.Right;
            _lastNodeFound = treeNode;
            return treeNode.Key;
        }
        /// <summary>
        /// Returns the object having the minimum key value
        /// </summary>
        /// <returns>Object data value</returns>
        public object GetMinValue()
        {
            return GetData(GetMinKey());
        }
        /// <summary>
        /// Returns the object having the maximum key
        /// </summary>
        /// <returns>Object data value</returns>
        public object GetMaxValue()
        {
            return GetData(GetMaxKey());
        }
        /// <summary>
        /// Returns an enumerator that returns the tree nodes in order
        /// </summary>
        /// <returns>RBTreeEnumerator</returns>
        public RBTreeEnumerator GetEnumerator()
        {
            //elements is simply a generic name to refer to the 
            //data objects the nodes contain
            return Elements(true);
        }
        /// <summary>
        /// Ascending if true, the keys will be returned ascending order, 
        /// else the keys will be returned in descending order.
        /// </summary>
        /// <returns>RB Tree Enumerator</returns>
        public RBTreeEnumerator Keys()
        {
            return Keys(true);
        }
        /// <summary>
        /// The keys in set order
        /// </summary>
        /// <param name="ascending">True or False</param>
        /// <returns>RB Tree Enumerator</returns>
        public RBTreeEnumerator Keys(bool ascending)
        {
            return new RBTreeEnumerator(_rbTree, true, ascending);
        }
        /// <summary>
        /// Values
        /// </summary>
        /// <returns>RB Tree Enumerator</returns>
        public RBTreeEnumerator Values()
        {
            return Elements(true);
        }
        /// <summary>
        /// If(_ascending is true, the objects will be returned in _ascending order,
        /// else the objects will be returned in descending order.
        /// </summary>
        /// <returns>An enumeration of the data objects</returns>
        public RBTreeEnumerator Elements()
        {
            return Elements(true);
        }
        /// <summary>
        /// The objects in set order
        /// </summary>
        /// <param name="ascending">True or False</param>
        /// <returns>An enumeration of the data objects</returns>
        public RBTreeEnumerator Elements(bool ascending)
        {
            return new RBTreeEnumerator(_rbTree, false, ascending);
        }
        /// <summary>
        /// Checks if the tree is empty
        /// </summary>
        /// <returns>True or False</returns>
        public bool IsEmpty()
        {
            return (_rbTree == null);
        }
        /// <summary>
        /// Removes the key and data object (delete)
        /// </summary>
        /// <param name="key">Key value</param>
        public void Remove(IComparable key)
        {
            if (key == null)
                throw (new RBTreeException("RB Tree Node key is null"));
            var result = key.CompareTo(_lastNodeFound.Key);
            //find next node
            RBTreeNode node;
            //see if next node to be deleted was the last one found
            if (result == 0)
                node = _lastNodeFound;
            else
            {//not found, must search		
                node = _rbTree;
                while (node != SentinelNode)
                {
                    result = key.CompareTo(node.Key);
                    if (result == 0)
                        break;
                    node = result < 0 ? node.Left : node.Right;
                }
                if (node == SentinelNode)
                    return;//key not found
            }
            Delete(node);
            _intCount = _intCount - 1;
        }
        /// <summary>
        /// Delete a next node from the tree and restore RB properties
        /// </summary>
        /// <param name="zRBTreeNode">RBTreeNode</param>
        private void Delete(RBTreeNode zRBTreeNode)
        {
            //A nextNode to be deleted will be: 
            //	1. a leaf with no children
            //	2. have one child
            //	3. have two children
            //If the deleted nextNode is red, the red black properties still hold.
            //If the deleted nextNode is black, the tree needs rebalancing
            RBTreeNode y;//work nextNode 
            //find the replacement nextNode (the successor to xNode) - 
            //the nextNode one with at *most* one child. 
            if (zRBTreeNode.Left == SentinelNode || zRBTreeNode.Right == SentinelNode)
                y = zRBTreeNode;//nextNode has sentinel as a child
            else
            {
                //zRBTreeNode has two children, find replacement nextNode which will 
                //be the leftmost nextNode greater than zRBTreeNode
                y = zRBTreeNode.Right;//traverse right subtree	
                while (y.Left != SentinelNode)//to find next nextNode in sequence
                    y = y.Left;
            }
            //at this point, y contains the replacement nextNode. 
            //it's content will be copied to the valules in the nextNode to be deleted
            //xNode (y's only child) is the nextNode that will be linked to y's old parent.
            var x = y.Left != SentinelNode ? y.Left : y.Right;
            //replace xNode's parent with y's parent and
            //link xNode to proper subtree in parent
            //this removes y from the chain
            x.Parent = y.Parent;
            if (y.Parent != null)
                if (y == y.Parent.Left)
                    y.Parent.Left = x;
                else
                    y.Parent.Right = x;
            else
                _rbTree = x;//make xNode the root nextNode
            //copy the values from y (the replacement nextNode) 
            //to the nextNode being deleted.
            //note: this effectively deletes the nextNode. 
            if (y != zRBTreeNode)
            {
                zRBTreeNode.Key = y.Key;
                zRBTreeNode.Data = y.Data;
            }
            if (y.Color == RBTreeNode.Black)
                RestoreAfterDelete(x);
            _lastNodeFound = SentinelNode;
        }
        /// <summary>
        /// Deletions from RB trees may destroy the RB properties. 
        /// Examine the tree and restore. Rotations are normally required to restore it
        /// </summary>
        /// <param name="xNode">RBTreeNode</param>
        private void RestoreAfterDelete(RBTreeNode xNode)
        {
            //maintain RB tree balance after deleting nextNode 			
            RBTreeNode y;
            while (xNode != _rbTree && xNode.Color == RBTreeNode.Black)
            {
                if (xNode == xNode.Parent.Left)//determine sub tree from parent
                {
                    y = xNode.Parent.Right;//y is xNode's sibling 
                    if (y.Color == RBTreeNode.Red)
                    {//xNode is black, y is red - make both black and rotate
                        y.Color = RBTreeNode.Black;
                        xNode.Parent.Color = RBTreeNode.Red;
                        RotateLeft(xNode.Parent);
                        y = xNode.Parent.Right;
                    }
                    if (y.Left.Color == RBTreeNode.Black &&
                        y.Right.Color == RBTreeNode.Black)
                    {//children are both black
                        y.Color = RBTreeNode.Red;//change parent to red
                        xNode = xNode.Parent;//move up the tree
                    }
                    else
                    {
                        if (y.Right.Color == RBTreeNode.Black)
                        {
                            y.Left.Color = RBTreeNode.Black;
                            y.Color = RBTreeNode.Red;
                            RotateRight(y);
                            y = xNode.Parent.Right;
                        }
                        y.Color = xNode.Parent.Color;
                        xNode.Parent.Color = RBTreeNode.Black;
                        y.Right.Color = RBTreeNode.Black;
                        RotateLeft(xNode.Parent);
                        xNode = _rbTree;
                    }
                }
                else
                {//right subtree - same as code above with right and left swapped
                    y = xNode.Parent.Left;
                    if (y.Color == RBTreeNode.Red)
                    {
                        y.Color = RBTreeNode.Black;
                        xNode.Parent.Color = RBTreeNode.Red;
                        RotateRight(xNode.Parent);
                        y = xNode.Parent.Left;
                    }
                    if (y.Right.Color == RBTreeNode.Black &&
                        y.Left.Color == RBTreeNode.Black)
                    {
                        y.Color = RBTreeNode.Red;
                        xNode = xNode.Parent;
                    }
                    else
                    {
                        if (y.Left.Color == RBTreeNode.Black)
                        {
                            y.Right.Color = RBTreeNode.Black;
                            y.Color = RBTreeNode.Red;
                            RotateLeft(y);
                            y = xNode.Parent.Left;
                        }
                        y.Color = xNode.Parent.Color;
                        xNode.Parent.Color = RBTreeNode.Black;
                        y.Left.Color = RBTreeNode.Black;
                        RotateRight(xNode.Parent);
                        xNode = _rbTree;
                    }
                }
            }
            xNode.Color = RBTreeNode.Black;
        }
        /// <summary>
        /// Removes the next node with the minimum key
        /// </summary>
        public void RemoveMin()
        {
            if (_rbTree == null)
                throw (new RBTreeException("RBTreekNode is null"));
            Remove(GetMinKey());
        }
        /// <summary>
        /// Removes the next node with the maximum key
        /// </summary>
        public void RemoveMax()
        {
            if (_rbTree == null)
                throw (new RBTreeException("RBTreeNode is null"));
            Remove(GetMaxKey());
        }
        /// <summary>
        /// Empties or clears the tree
        /// </summary>
        public void Clear()
        {
            _rbTree = SentinelNode;
            _intCount = 0;
        }
        /// <summary>
        /// Size
        /// </summary>
        /// <returns>The size (number of nodes) in the tree</returns>
        public int Size()
        {
            return _intCount;
        }
        public RBTreeEnumerator GetRoot()
        {
            var myEnumerator = GetEnumerator();
            while (myEnumerator.MoveNext())
            {
                if (myEnumerator.ParentKey == null)
                    return myEnumerator;
            }
            return null;
        }
        /// <summary>
        /// Equals
        /// </summary>
        /// <param name="obj">Value</param>
        /// <returns>True or False</returns>
        public override bool Equals(object obj)
        {
            return obj != null &&
                ((obj is RBTreeNode) && (this == obj || (ToString().Equals(obj.ToString()))));
        }
        /// <summary>
        /// HashCode
        /// </summary>
        /// <returns>int</returns>
        public override int GetHashCode()
        {
            return _intHashCode;
        }
        /// <summary>
        /// ToString
        /// </summary>
        /// <returns>Identifier</returns>
        public override string ToString()
        {
            return _strIdentifier;
        }
    }
}